package 算法.图.有向图;

import 算法.图.util.DirectedEdge;
import edu.princeton.cs.algs4.Bag;
import edu.princeton.cs.algs4.IndexMinPQ;
import edu.princeton.cs.algs4.MinPQ;
import edu.princeton.cs.algs4.Stack;

/**
 * 【最短路径问题：有向图：狄杰斯卡尔算法】
 * 		求出从某个点start到所有点得最短路径
 * @Date   2017-09-04 18：00
 * @author Administrator
 * @version TODO:>>>>>>>尚未测试
 */
public class DijkstraSP {
	public EdgeWeightedDigraph G;			//有向图
	public IndexMinPQ<Double> pq;			//优先队列
	public DirectedEdge[]  edgeTo;				
	public double[] 		distTo;
	public int start;						//开始节点
	public DijkstraSP(EdgeWeightedDigraph G, int start) {
		this.G      = G;
		this.pq     = new IndexMinPQ<Double>(G.V);
		this.edgeTo = new DirectedEdge[G.V];
		this.distTo = new double[G.V];
		this.start  = start;
		
		for (int i = 0; i < G.V; i ++) {
			distTo[i] = Double.POSITIVE_INFINITY;		//无限大，初始化表示所有点均不可达
		}
		
		edgeTo[0] = null;								//0索引没用
		distTo[0] = 0d;
		pq.insert(0, 0d);
		
		while (!pq.isEmpty()) {
			relax(pq.delMin());
		}
	}
	private void relax(int v) {
		Bag<DirectedEdge> adjs = G.adjs[v];
		for (DirectedEdge edge : adjs) {
			int w = edge.to();
			if(distTo[w] > distTo[v]+edge.getWeight()) {
				distTo[w] = distTo[v]+edge.getWeight();
				edgeTo[w] = edge;
				if (pq.contains(w))	pq.change(w, edge.getWeight());
				else				pq.insert(w, edge.getWeight());
			}
		}
	}
	
	/**
	 * 到某个顶点是否存在路径
	 * @param w
	 * @return
	 */
	public boolean hasPath(int w) {
		return distTo[w] < Double.POSITIVE_INFINITY;
	}
	
	/**
	 * 得到到某个点的完整路径
	 * @param w
	 */
	public Stack<DirectedEdge> getPath(int w) {
		Stack<DirectedEdge> path = null;
		if(hasPath(w)) {
			path = new Stack<>();
			DirectedEdge edge;
			for (edge=edgeTo[w]; edge!=null; w=edge.from()) {
				edge=edgeTo[w];
				path.push(edge);
			}
		}
		return path;
	}
}
